package com.zlk.algorithm.dataStructure.graph.topological;

import com.zlk.algorithm.dataStructure.graph.impl.GraphList;
import org.junit.Test;

import java.util.ArrayList;
/**
 * @program: algorithm
 * @ClassName TopologicalOrderBFS2
 * @description:https://www.nowcoder.com/questionTerminal/88f7e156ca7d43a1a535f619cd3f495c
 * @author: slfang
 * @create: 2024-03-20 10:46
 * @Version 1.0
 **/
public class TopologicalOrderBFS2 {

    //给定一个包含
    //n个点
    //m条边的有向无环图，求出该图的拓扑序。若图的拓扑序不唯一，输出任意合法的拓扑序即可。若该图不能拓扑排序，输出
    //−1。

    //输入描述:
    //第一行输入两个整数
    //n,m (1≤n ,m<=2*10^5)表示点的个数和边的条数。
    //接下来的
    //m行，每行输入两个整数a ，b (1<=a,b<=n) 表示a到b之间有一条有向边
    //ex:
    //输入
    //5 4
    //1 2
    //2 3
    //3 4
    //4 5

    //输出
    //1 2 3 4 5











    public ArrayList<Integer> topSort(int[][] graph){
        int size = graph[0][0];
        GraphList graphList = new GraphList(size);
        for (int i = 1; i <graph.length ; i++) {
            graphList.addEdge(graph[i][0]-1,graph[i][1]-1);
        }
        ArrayList<Integer> sort1 = graphList.sort();
        ArrayList<Integer> ans = new ArrayList<>();

        //可以将val位置封装成对象 一个表示位置一个表示val
        for (int i = 0; i < sort1.size(); i++) {
            ans.add(i+1);
        }
        return ans;
    }

    @Test
    public void test(){
        int[][] matrix = new int[5][2];
        int[] a0 = new int[]{5,4};
        int[] a1 = new int[]{1,2};
        int[] a2 = new int[]{2,3};
        int[] a3 = new int[]{3,4};
        int[] a4 = new int[]{4,5};
        matrix[0]=a0;
        matrix[1]=a1;
        matrix[2]=a2;
        matrix[3]=a3;
        matrix[4]=a4;
        System.out.println(topSort(matrix));
    }


}
